package week07

// 212. 单词搜索 II
// https://leetcode-cn.com/problems/word-search-ii/

func findWords(board [][]byte, words []string) []string {
	// 构造字典树
	trie := newTrie()
	for _, word := range words {
		trie.insert(word)
	}

	var ans []string
	for x := range board {
		for y := range board[x] {
			visit := make(map[int]bool)
			visit[hash(x, y)] = true
			res := dfs(board, trie.root, x, y, visit, []string{})
			ans = append(ans, res...)
		}
	}
	return ans
}

func dfs(board [][]byte, curr *Node, x, y int, visit map[int]bool, ans []string) []string {
	var father = curr
	curr, ok := curr.child[board[x][y]]
	if !ok {
		return ans
	}
	if curr.word != "" {
		ans = append(ans, curr.word)
		curr.word = ""
	}
	if len(curr.child) == 0 {
		delete(father.child, board[x][y])
	}

	for dir := range dx {
		nx := x + dx[dir]
		ny := y + dy[dir]
		if visit[hash(nx, ny)] {
			continue
		}
		if !isValid(board, nx, ny) {
			continue
		}
		visit[hash(nx, ny)] = true
		ans = dfs(board, curr, nx, ny, visit, ans)
		visit[hash(nx, ny)] = false
	}
	return ans
}

func isValid(board [][]byte, x, y int) bool {
	return x >= 0 && y >= 0 && x < len(board) && y < len(board[x])
}

func hash(x, y int) int {
	return x * 13 + y
}


var dx = [4]int{0, 1, 0, -1}
var dy = [4]int{1, 0, -1, 0}

type Node struct {
	word string
	child map[byte]*Node
}

func newNode() *Node {
	return &Node{
		word: "",
		child: make(map[byte]*Node),
	}
}

func newTrie() *Trie {
	return &Trie {
		root: newNode(),
	}
}

type Trie struct {
	root *Node
}

func (t *Trie) insert(word string) {
	var curr = t.root
	for _, b := range []byte(word) {
		next, ok := curr.child[b]
		if !ok {
			next = newNode()
			curr.child[b] = next
		}
		curr = next
	}
	curr.word = word
}